//找出和为一目标数的不同组合，可以重复选取元素
#include <vector>
#include <algorithm>
using std::sort;
using std::vector;
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& candidates,int target,int startIndex,int sum){
    if(sum==target){
        result.push_back(path);
        return ;
    }
                                                //进行剪枝，若下一个大于target，则不继续递归（要先排序数组）
    for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){
        path.push_back(candidates[i]);
        sum+=candidates[i];
        backtracking(candidates,target,i,sum);              //i表示可以重复选自己
        sum-=candidates[i];
        path.pop_back();
    }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(),candidates.end());
    backtracking(candidates,target,0,0);
    return result;
}
